package sword.chapter8Tree;

/**
 * 二叉树剪枝
 *
 * 深度优先搜索 后序遍历
 * 递归返回条件       root==null
 * 当前层业务处理     root.left == null && root.right == null && root.val == 0 返回null
 *
 * @author K
 * @date 2021-12-06 21:02
 */
public class S47PruneTree {
    public static TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(0);
        TreeNode node3 = new TreeNode(0);
        TreeNode node4 = new TreeNode(0);
        TreeNode node5 = new TreeNode(0);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(1);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        TreeNode result = pruneTree(root);
        System.out.println();
    }
}
